package p1;

import org.junit.Test;

import java.util.*;

public class LeetcodeTest_1 {

    /**
     *  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     *     你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *     你可以按任意顺序返回答案。
     *         示例 1：
     *         输入：nums = [2,7,11,15], target = 9
     *         输出：[0,1]
     *         解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     *         输入：nums = [3,2,4], target = 6
     *         输出：[1,2]
     */
    @Test
    public void t1(){
        int[] nums = {3,2,4};
        int [] result = twoSum(nums, 6);
        System.out.println("方式一:" + Arrays.toString(result));

        int [] result2 = twoSum2(nums, 6);
        System.out.println("方式二:" + Arrays.toString(result2));
    }

    /**
     * 暴力的解法是两层for循环查找，时间复杂度是O(n^2)
     */
    public int [] twoSum(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int value = target - num;
            for (int j = nums.length - 1; j >= 0; j--) {
                if (value == nums[j] && i != j){
                    list.add(i);
                    list.add(j);
                }
            }
        }
        return list.stream().distinct().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 时间复杂度0(n)
     * 这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。
     * 那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标
     * 所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下表}。
     * 在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。
     */
    public int [] twoSum2(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(target - num)){
                set.add(map.get(target - num));
                set.add(i);
            }else {
                map.put(num,i);
            }
        }
        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}
